跳到主要内容

QR 分解

1. 正交矩阵​

设正交矩阵 QQ，则 Qx⃗Q\vec x 的 2-范数不变。

正交矩阵相当于对 x⃗\vec x 进行了压缩

2. 正交三角分解​

设 Am×nA_{m\times n} 的秩为 nn，则 AA 可以唯一地分解为 Am×n=Qm×nRn×nA_{m\times n} = Q_{m\times n}R_{n\times n}，其中 QQ 为标准正交向量组矩阵，RR 为正线上三角阵。

3. Gram-Schimidt QR 分解​

设矩阵 AA 的列向量为 a⃗1,a⃗2,⋯ ,a⃗n\vec a_1, \vec a_2, \cdots, \vec a_n，则 Gram-Schimidt QR 分解的步骤如下：

3.1 获取正交基​

令 u⃗1=a⃗1\vec u_1 = \vec a_1，接下来 u⃗2=a⃗2−(u⃗1,a⃗2)(u⃗1,u⃗1)u1⃗\vec u_2 =\vec a_2 - \frac{(\vec u_1,\vec a_2)}{(\vec u_1,\vec u_1)}\vec{u_1}，...

以此类推，

u⃗k=a⃗k−∑i=1k−1(u⃗i,a⃗k)(u⃗i,u⃗i)ui⃗\vec u_k = \vec a_k - \sum_{i=1}^{k-1} \frac{(\vec u_i,\vec a_k)}{(\vec u_i,\vec u_i)}\vec{u_i}

3.2 归一化​

令 e⃗k=u⃗k∥u⃗k∥\vec e_k = \frac{\vec u_k}{\|\vec u_k\|}，则 e⃗1,e⃗2,⋯ ,e⃗n\vec e_1, \vec e_2, \cdots, \vec e_n 为正交标准基。故

Q=[e⃗1,e⃗2,⋯ ,e⃗n]Q = [\vec e_1, \vec e_2, \cdots, \vec e_n]

3.3 求上三角阵​

R=[e⃗1Ta⃗1e⃗1Ta⃗2⋯e⃗1Ta⃗n0e⃗2Ta⃗2⋯e⃗2Ta⃗n⋮⋮⋱⋮00⋯e⃗nTa⃗n]R = \begin{bmatrix} \vec e_1^T\vec a_1 & \vec e_1^T\vec a_2 & \cdots & \vec e_1^T\vec a_n \\ 0 & \vec e_2^T\vec a_2 & \cdots & \vec e_2^T\vec a_n \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \vec e_n^T\vec a_n \end{bmatrix}

综上，A=QRA=QR

4. Household 反射法 QR 分解​

设矩阵 A=(a⃗1,a⃗2,⋯ ,a⃗n)A = (\vec a_1, \vec a_2, \cdots, \vec a_n)，则 AA 的 QR 分解：

4.1 获取反射矩阵​

取 e⃗=(1,0,⋯ ,0)\vec e = (1,0,\cdots, 0)

取

v⃗1=a⃗1+sgn(a11)∥a⃗1∥e⃗\vec v_1 = \vec a_1 + sgn(a_{11})\Vert\vec a_1\Vert \vec e

再将其归一化得 u⃗1=v⃗∥v⃗∥\vec u_1 = \frac{\vec v}{\Vert\vec v\Vert}

则反射矩阵为

H1=I−2u⃗1u⃗1TH_1 = I - 2\vec u_1 \vec u_1^T

4.2 更新矩阵​

获得矩阵

H1A=[∗∗0A^]H_1A = \begin{bmatrix} * & * \\ 0 & \hat{A} \end{bmatrix}

4.3 迭代​

对 A^\hat{A} 进行同样的操作，获得 H^2\hat H_2，进而取得矩阵

H2=[100H^2]H_2 = \begin{bmatrix} 1 & 0 \\ 0 & \hat H_2 \end{bmatrix}

反复迭代，有 HnHn−1⋯H2H1A=RH_nH_{n-1}\cdots H_2H_1 A = R

故 Q=∏k=1nHkTQ=\prod_{k=1}^{n}H_k^T